package com.feng.leetcode;

/**
 * @author feng
 * @decrition
 * @date 2022/5/130:15
 */
public class L44 {
    public static void main(String[] args) {
        String str = "";
        String pat = "****";
        boolean match = isMatch(str, pat);
        System.out.println(match);
    }

    public static boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        while (i < s.length() && j < p.length()) {
            char c = p.charAt(j);
            char orign = s.charAt(i);
            if ('?' == c) {
                return isMatch(s.substring(i + 1), p.substring(j + 1));
            }
            if ('*' == c) {
                if (j + 1 == p.length()) {
                    return true;
                } else {
                    char pattern = p.charAt(j + 1);
                    String substring = s.substring(i);
                    while (substring.contains(pattern + "")) {
                        int i1 = substring.indexOf(pattern);
                        substring = substring.substring(i1);
                        boolean match = isMatch(substring, p.substring(j + 1));
                        if (match) {
                            return true;
                        }
                        substring = substring.substring(i1 + 1);
                    }
                    return false;
                }
            }
            if (c != orign) {
                return false;
            }
            i++;
            j++;
        }
        if (i <= s.length() && j <= p.length()) {
            return true;
        }
        return false;
    }

}
